package 图.最短路径;


import 抽象数据类型.DirectedEdge;
import 抽象数据类型.EdgeWeightedGraph;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @description:
 * @author: ywk
 * @date: 2021-08-15
 */
public class 基于队列的BellmanFord算法 {
    public static void main(String[] args) {
        int[] arr1 = {0, 1, 0, 1, 1, 4, 2, 3};
        int[] arr2 = {1, 2, 2, 4, 3, 3, 3, 1};
        double[] weight = {1, 2, 3, 2, -3, -3, -2, 3};
        EdgeWeightedGraph G = new EdgeWeightedGraph(arr1.length);
        G.addGraph(arr1, arr2, weight);
        BellmanFOrdSP dijkstraSP = new BellmanFOrdSP(G, 0);
        System.out.println(dijkstraSP.distTo(3));
        for (DirectedEdge edge : dijkstraSP.pathTo(3)) {
            System.out.println(edge);
        }
    }

    public static class BellmanFOrdSP {
        private double[] distTo;
        private DirectedEdge[] edgeTo;
        private boolean[] onQ; //判断该顶点是否还存在队列中
        private Queue<Integer> queue;
        private int cost; //relax()的调用次数
        private Iterable<DirectedEdge> cycle;//edgeTo[]中是否含有负权重环

        public BellmanFOrdSP(EdgeWeightedGraph G, int s) {
            distTo = new double[G.V()];
            edgeTo = new DirectedEdge[G.V()];
            onQ = new boolean[G.V()];
            queue = new LinkedList<>();
            for (int v = 0; v < G.V(); v++) {
                distTo[v] = Double.POSITIVE_INFINITY;
            }
            distTo[s] = 0;
            queue.offer(s);
            onQ[s] = true;
            while (!queue.isEmpty() && !hasNegativeCycle()) {
                int v = queue.poll();
                relax(G, v);
            }

        }

        private void relax(EdgeWeightedGraph g, int v) {
            for (DirectedEdge e : g.adj(v)) {
                int w = e.to();
                if (distTo[w] > distTo[v] + e.weight()) {
                    distTo[w] = distTo[v] + e.weight();
                    edgeTo[w] = e;
                    if (!onQ[w]) {
                        queue.offer(w);
                        onQ[w] = true;
                    }
                }
                if (cost++ % g.V() == 0) {
                    findNegativeCycle();
                }

            }
        }

        public  void findNegativeCycle() {
            int V = edgeTo.length;
            EdgeWeightedGraph spt = new EdgeWeightedGraph(V);
            for (int v = 0; v < V; v++) {
                if (edgeTo[v] != null) {
                    spt.addEdge(edgeTo[v]);
                }
            }
            EdgeWeightedCycleFinder cf = new EdgeWeightedCycleFinder(spt);
            cycle = cf.cycle();

        }

        public boolean hasNegativeCycle() {
            return cycle != null;
        }

        public Iterable<DirectedEdge> negativeCycle() {
            return cycle;
        }

        public Iterable<DirectedEdge> pathTo(int v) {
            if (!hasPathTo(v)) {
                return null;
            }
            Stack<DirectedEdge> path = new Stack();
            for (DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()]) {
                path.push(e);
            }
            return path;
        }

        private boolean hasPathTo(int v) {
            return Double.POSITIVE_INFINITY != distTo[v];
        }

        public double distTo(int i) {
            return distTo[i];
        }

        static class EdgeWeightedCycleFinder {
            private boolean[] marked;
            private DirectedEdge[] edgeTo;
            private Stack<DirectedEdge> cycle;//有向环的所有顶点
            private boolean[] onStack; //递归条用栈上的所有顶点

            public EdgeWeightedCycleFinder(EdgeWeightedGraph g) {
                onStack = new boolean[g.V()];
                edgeTo = new DirectedEdge[g.V()];
                marked = new boolean[g.V()];
                for (int i = 0; i < g.V(); i++) {
                    if (!marked[i]) {
                        dfs(g, i);
                    }
                }
            }

            private void dfs(EdgeWeightedGraph g, int v) {
                onStack[v] = true;
                marked[v] = true;
                for (DirectedEdge e : g.adj(v)) {
                    int w = e.to();
                    if (this.hasCycle()) {
                        return;
                    } else if (!marked[w]) {
                        edgeTo[w] = e;
                        dfs(g, w);
                    } else if (onStack[w]) {
                        for (DirectedEdge edge = edgeTo[v]; edge != null; edge = edgeTo[e.from()]) {
                            cycle.push(edge);
                        }
                    }
                }
                onStack[v] = false;
            }

            public boolean hasCycle() {
                return cycle != null;
            }

            public Iterable<DirectedEdge> cycle() {
                return cycle;
            }
        }
    }
}
